#pragma once
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

/**
 * 二叉树节点结构
 */
typedef struct binaryTreeNode
{
  int value;
  struct binaryTreeNode* left;
  struct binaryTreeNode* right;
} BTNode;

/**
 * 描述：二叉树的前、中、后序遍历
 * 输入参数：
 *      root：二叉树根节点
 * 输出参数：按前、中、后序方式逐个打印二叉树节点的值
 * 返回值：无
 */
void
PreOrder(BTNode* root);

void
InOrder(BTNode* root);

void
PostOrder(BTNode* root);

/**
 * 描述：求二叉树的节点个数
 * 输入参数：
 *      root：二叉树根节点
 * 输出参数：无
 * 返回值：二叉树的节点个数
 */
int
TreeSize(BTNode* root);

/**
 * 描述：求二叉树的叶子节点个数
 * 输入参数：
 *      root：二叉树根节点
 * 输出参数：无
 * 返回值：二叉树的叶子节点个数
 */
int
TreeLeaf(BTNode* root);

/**
 * 描述：求二叉树高度
 * 输入参数：
 *      root：二叉树根节点
 * 输出参数：无
 * 返回值：二叉树的高度
 */
int
TreeHeight(BTNode* root);

/**
 * 描述：求二叉树第k层节点个数
 * 输入参数：
 *      root：二叉树根节点
 * 输出参数：无
 * 返回值：二叉树第k层节点个数
 */
int
TreeKSize(BTNode* root, int k);

/**
 * 描述：在二叉树中查找值为x的节点
 * 输入参数：
 *      root：二叉树根节点
 *      x：
 * 输出参数：无
 * 返回值：目标节点
 */
BTNode*
TreeFind(BTNode* root, int x);

/**
 * 描述：判断是否为单值二叉树
 */
bool
isUnivalTree(BTNode* root);

/**
 * 描述：判断两颗二叉树是否相同
 */
bool
isSameTree(BTNode* p, BTNode* q);

/**
 * 描述：判断一个树是不是另一颗树的子树
 */
bool
isSubtree(BTNode* root, BTNode* subRoot);

/**
 * 描述：根据一段前序序列的字符串重建二叉树
 * 输入参数：
 *      str：前序序列的字符串，例如ABC##DE#G##F###，其中#代表空树
 *      pi：表示指向str某个字符的地址，需要传址调用
 */
BTNode*
reBuildBinaryTree(char* str, int* pi);